/*
 * @lc app=leetcode.cn id=5 lang=java
 *
 * [5] 最长回文子串
 */

// @lc code=start
class Solution {
    /**
     * 有超时问题，双层循环还是太暴力了。
     * 看了看题目讨论，有了个新思路
     * 把回文看成从中间字符出发，两边必定相互对称的字符串
     */
    /*
    public String longestPalindrome(String s) {
        int max = 0;
        String maxS = "";
        for(int i =0;i<s.length();i++){
            for(int j = i ;j<s.length();j++){
                if(judge(i, j, s)){//是回文串
                    if(j-i+1 > max){
                        max = j-i+1;
                        maxS = s.substring(i, j+1);
                    }
                }
            }
        }
        return maxS;
        
    }
    public boolean judge(int begin ,int end, String s){//用来判断是否是一个回文串
        while(end>begin){
            if(s.charAt(begin)==s.charAt(end) ){
                begin++;
                end--;
            }else{
                return false;
            }
        }
        return true;
    }
    */
    int begin =0 ,end =0;
    public String longestPalindrome(String s) {
        if(s.length() == 0 || s == null ){
            return "";
        }
        char[] str = s.toCharArray();

        for(int i = 0 ;i<s.length();i++){
            i = findAns(i, str);
        }


        return s.substring(begin, end+1);

    }
    public int findAns(int a , char[] str){
        int b = a;
        //这一步很关键，找中间相同的部分，可能只是1个字符b，也可能是bbbb这样的
        while( b < str.length -1 && str[a] == str[b+1]){//注意b不要越级
            b++;
        }
        
        //记录最后一个相同的字符，应为显然没必要在这几个相同的字符中间找回文了，直接把i迭代过去即可。
        int ans = b;
        while( a>0 && b<str.length-1 && str[a-1] == str[b+1]){//这个地方这么写是为了防止指针越界
            a--;
            b++;
        }
        if(b-a>end-begin){
            end=b;
            begin=a;
        }
        

        return ans;
    }
}
// @lc code=end

